package dome3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description: 包装类,链表作业题
 * User: 王圆豪
 * Date: 2024-07-16
 * Time: 13:10
 */

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}
class Solution {
    public static void main2(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(1);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode listNode = partition(listNode1, 3);
        ListNode cur = listNode;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    public static void main3(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(2);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        System.out.println(chkPalindrome(listNode2));
    }

    public static void main4(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(2);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        System.out.println(detectCycle(listNode1));
    }
    //求环的入口点
    public static ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            }else {
                return null;
            }
            if (fast == slow) {
                slow = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode phead = new ListNode(-1);
        ListNode prev = phead;
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val > cur2.val) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            } else {
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }
        }
        if (cur1 == null) {
            prev.next = cur2;
        }
        if (cur2 == null) {
            prev.next = cur1;
        }
        return phead.next;
    }
    //判断链表带环
    public static boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            if (fast == slow){
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }
    //判定链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int count1 = 0;
        int count2 = 0;
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        while (cur1.next != null) {
            count1++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            count2++;
            cur2 = cur2.next;
        }
        int count = Math.abs(count2 - count1);
        if (count1 >= count2) {
            cur1 = headB;
            cur2 = headA;
        }
        if (count1 < count2) {
            cur1 = headA;
            cur2 = headB;
        }
        while (count-- != 0){
            cur2 = cur2.next;
        }
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) {
                break;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
    //判定链表是否是回文（面试题）
    public static boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) {
            return true;
        }
        //找中间节点
        ListNode slow = A;
        ListNode fast = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //后半部分转置
        ListNode cur = slow.next;
        ListNode curN = slow;
        while (slow.next != null) {
            slow.next = cur.next;
            cur.next = curN;
            curN = cur;
            cur = slow.next;
        }
        //遍历
        while (A != slow) {
            if (A.val != curN.val) {
                return false;
            }
            A = A.next;
            curN = curN.next;
        }
        return true;
    }
    //给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
    public static ListNode partition(ListNode pHead, int x) {
        ListNode head1 = new ListNode(-1);
        ListNode head2 = new ListNode(-1);
        ListNode cur = pHead;
        ListNode pre1 = head1;
        ListNode pre2 = head2;
        while (cur != null) {
            if (cur.val < x){
                pre1.next = cur;
                pre1 = cur;
            } else {
                pre2.next = cur;
                pre2 = cur;
            }
            cur = cur.next;
        }
        if (head2.next != null) {
            pre2.next = null;
        }
        if (head1.next == null) {
            return head2.next;
        }
        pre1.next = head2.next;
        return head1.next;
    }
    //获取链表倒数第K个节点
    public static ListNode getListNode(ListNode head, int pos){
        ListNode slow = head;
        ListNode fast = head;
        while (pos > 1) {
            fast = fast.next;
            pos--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    //单链表的逆置
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head.next;
        ListNode curN = head;
        while (cur != null) {
            head.next = cur.next;
            cur.next = curN;
            curN = cur;
            cur = head.next;
        }
        return curN;
    }
    //删除链表中所有值为value的元素
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur = new ListNode(-1);
        cur.next = head;
        ListNode tmp = cur;
        while (tmp.next != null) {
            if (tmp.next.val == val) {
                tmp.next = tmp.next.next;
            }else {
                tmp = tmp.next;
            }
        }
        return cur.next;
    }
    //获取链表的中间节点
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    //杨辉三角形
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list1 = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    list1.add(1);
                }else {
                    list1.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
                }
            }
            list.add(list1);
        }
        return list;
    }
    public static int removeElement(int[] nums, int val) {
        int count1 = 0;
        for (int i = 0; i < nums.length; i++) {
                if (nums[i] == val) {
                    count1++;
                }else {
                    nums[i - count1] = nums[i];
                }
        }
        return nums.length - count1;
    }

    public static void main1(String[] args) {
        int[] nums = new int[]{0,1,2,2,3,0,4,2};
        int a = removeElement(nums, 2);
        System.out.println(a);
        System.out.println(Arrays.toString(nums));
    }

    public void rotate(int[] nums, int k) {
        k %= nums.length;
        ud(nums, 0, nums.length);
        ud(nums, 0, k - 1);
        ud(nums, k, nums.length - 1);
    }

    public void ud(int[] nums, int h, int k) {
        int i = h;
        int j = k;
        while(i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}
public class Main {
}
